<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1">

<meta name="description" content="Visualize and simulate Turing machines as animated state diagrams.
Create and share your own machines using a simple format. Examples and exercises are included.">
<meta name="keywords" content="Turing machine, finite automata, simulator, visualization, state diagram">
<meta name="robots" content="NOODP">
<title>Turing machine visualization</title>

<!-- Bootstrap -->
<link href="https://maxcdn.bootstrapcdn.com/bootswatch/3.3.6/lumen/bootstrap.min.css" rel="stylesheet"
integrity="sha384-mvYjhBJXQ9VlNETV/xXShy849GsBHnKzVVudnMOcWUVM/6Nd2ksj8VNng5f8ylyX" crossorigin="anonymous">
<link href="https://maxcdn.bootstrapcdn.com/font-awesome/4.6.3/css/font-awesome.min.css" rel="stylesheet"
integrity="sha384-T8Gy5hrqNKT+hzMclPo118YTQO6cYprQmhrYwIiQ/3axmI1hQomh7Ud2hPOy8SP1" crossorigin="anonymous">
<!-- HTML5 Shim and Respond.js IE8 support of HTML5 elements and media queries -->
<!-- WARNING: Respond.js doesn"t work if you view the page via file:// -->
<!--[if lt IE 9]>
  <script src="https://oss.maxcdn.com/libs/html5shiv/3.7.2/html5shiv.js"></script>
  <script src="https://oss.maxcdn.com/libs/respond.js/1.4.2/respond.min.js"></script>
<![endif]-->

<!-- Libraries -->
<script src="https://cdn.jsdelivr.net/d3js/3.5.17/d3.min.js"
integrity="sha256-uB5nPcWK8vr5e83snqtMUYJ2n/5TZ3PV9CCRk1pzob4=" crossorigin="anonymous"></script>
<script src="https://cdn.jsdelivr.net/ace/1.2.3/noconflict/ace.js"
integrity="sha256-Iww1CLn76ly5OU/TUHhiQF9qYy+BpQpg8hI8sIhi32I=" crossorigin="anonymous"></script>

<script src="https://cdnjs.cloudflare.com/ajax/libs/js-yaml/3.6.0/js-yaml.min.js"
integrity="sha256-cClLF3hmu8Q/atb1MfoMUg+4h2MTXFMl5+UuvXBWE8g=" crossorigin="anonymous"></script>
<script src="https://cdn.jsdelivr.net/lodash/4.10.0/lodash.min.js"
integrity="sha256-WplZqoBFo5rcW50YJBm/A1DRy7NnlMHTVDZBan+g2ZU=" crossorigin="anonymous"></script>
<script> var lodash = _; </script>
<script src="https://cdn.jsdelivr.net/lodash/4.10.0/lodash.fp.min.js"
integrity="sha256-21hyGphPmEWw6dEv1N50zj2CGTCph/CZOkIQHqGoTfs=" crossorigin="anonymous"></script>
<script src="https://cdn.jsdelivr.net/bluebird/3.4.1/bluebird.min.js"
integrity="sha256-RerJKWlCVH4Or054aLxHuQ4EXbfVwjyYeT99oVAW1pg=" crossorigin="anonymous"></script>
<script src="https://cdn.jsdelivr.net/clipboard.js/1.5.12/clipboard.min.js"
integrity="sha256-YPxFEfHAzLj9n2T+2UXAKGNCRUINk0BexppujiVhRH0=" crossorigin="anonymous"></script>
<!-- jQuery (necessary for Bootstrap plugins) -->
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.3/jquery.min.js"
integrity="sha384-6ePHh72Rl3hKio4HiJ841psfsRJveeS+aLoaEf3BWfS+gTF0XdAqku2ka8VddikM" crossorigin="anonymous"></script>
<!-- Bootstrap: all compiled plugins -->
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/js/bootstrap.min.js"
integrity="sha384-0mSbJDEHialfmuBBQP6A4Qrprq5OVfW37PRR3j5ELqxss1yVqOtnepnHVP9aJ7xS" crossorigin="anonymous"></script>

<!-- CSS -->
<link href="build/state-diagram/StateViz.css" rel="stylesheet">
<link href="build/tape/tape.css" rel="stylesheet">
<style>
  body {
    font-variant-ligatures: contextual;
  }
  nav .navbar-right {
    margin-right: 0; /* override negative margin  */
  }
  .navbar-brand {
    font-variant: small-caps;
    letter-spacing: .03em; /* for caps */
    font-family: 'Avenir Next', 'Avenir', 'Lucida Grande',
      'Source Sans Pro', 'Helvetica Neue', Helvetica, Arial, sans-serif;
  }
  .kern { letter-spacing: -.1em; font-kerning: none; /* kern manually */ }
  .navbar-brand .kern-Ma { letter-spacing: 0em }
  .navbar-brand .kern-Vi { letter-spacing: -.02em }
  pre {
    background-color: hsl(0, 0%, 98%);
  }
  .editor-shortcuts td:first-child {
    text-align: right;
  }
  kbd { /* Adjusted StackOverflow's old <kbd> style https://meta.superuser.com/questions/4788 */
    background-color: #f7f7f7;
    border: 1px solid #ccc;
    border-radius: 3px;
    box-shadow: 0 1px 0 rgba(0,0,0,0.2), 0 0 0 2px #fff inset;
    color: #333;
    display: inline-block;
    font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif;
    font-size: 85%;
    line-height: 1.4;
    margin: 0 .1em;
    padding: .1em .6em;
    text-shadow: 0 1px 0 #fff;
  }
  @media (min-width: 992px) { /* when diagram and editor are side by side */
    /* Visually center diagram horiz. (match left and right negative space) */
    #diagram-column { padding-right: 0; }
  }
  /* Editor */
  #editor-wrapper {
    position: relative;
    width: 100%;
    max-width: 85ch;
    margin: auto;
  }
  button.tm-editor-revert {
    position: absolute;
    right: 0;
  }
  .tm-editor.ace_editor {
    border: 1px solid #DDD;
    /*border: 1px solid #ccc;*/
    border-radius: 4px;
    margin-top: 1em;
    font-family: 'Source Code Pro', 'source-code-pro', 'Monaco', 'Menlo', 'Ubuntu Mono', 'Consolas', monospace;
    text-align: left;
  }
  /* Print styles */
  @media print {
    button.btn, hr { display: none }
    #tutorial { page-break-before: always }
  }
  /* "Save" button */
  .btn-wide-save {
    padding-left: 1.5em;
    padding-right:1.5em;
  }
  /* Checkbox table */
  .checkbox-table tr > :first-child {
    text-align: right
  }
  .checkbox-table tr > :last-child {
    text-align: right;
  }
  .checkbox-table tbody tr, input[type="checkbox"] {
    cursor: pointer;
  }
  /* Disclosure triangle */
  a.disclosure-triangle {
    cursor: pointer;
    text-decoration: none;
  }
  a.disclosure-triangle:before {
    content: '▸';
    transform: rotate(90deg);
    transform-origin: center;
    transition: transform 0.1s linear;
    display: inline-block;
    font-size: larger;
    margin-right: 0.2em;
  }
  a.disclosure-triangle.collapsed:before {
    transform: none;
  }
  a.disclosure-triangle + div.collapse   > .panel:first-child,
  a.disclosure-triangle + div.collapsing > .panel:first-child {
    margin-top: 1em;
  }
  /* Page footer */
  .octicon.octicon-mark-github {
    fill: currentColor;
    overflow: visible;
  }
  .page-footer {
    margin: 2em 0 0 0;
    padding: 1.1em;
    border-top: 1px solid #ddd;
    background: hsl(0, 0%, 96%);
    text-align: center;
    line-height: 0; /* to center logo vertically */
  }
  .page-footer .octicon {
    color: hsl(0, 0%, 35%);
  }
  .page-footer a .octicon:hover {
    color: hsl(0, 0%, 0%);
  }
  /* Fix overflow inside modal caused by td pre */
  .modal-dialog td pre {
    white-space: pre-wrap;
    font-size: smaller;
  }
  /* Fix some cases of extra margins in bootstrap */
  .modal-body .panel:last-child,
  .panel-body > *:last-child {
    margin-bottom: 0;
  }
  /* Feature detection */
  .download-attr .download-fallback { display: none }
  .no-copycommand [data-clipboard-target] { display: none }

  .icon-help-block > * { display: table-cell }
  .icon-help-block > .glyphicon:first-child { padding-right: 0.5em }
</style>
<!-- Analytics -->
<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');

  ga('create', 'UA-81335742-1', 'auto');
  ga('send', 'pageview');

</script>
</head>



<body>
<nav class="navbar navbar-default">
  <div class="container-fluid">
    <div class="navbar-header">
      <span class="navbar-brand">
        <span class="kern">T</span>uring <span class="kern-Ma">M</span>achine <span class="kern-Vi">V</span>isualization
      </span>
    </div>

    <div class="navbar-form navbar-left">
      <!-- Document Menu -->
      <select id="tm-doc-menu" class="form-control"></select>
      <!-- Edit Menu -->
      <div class="btn-group">
        <button type="button" class="btn btn-default btn-sm dropdown-toggle"
        data-toggle="dropdown" aria-haspopup="true" aria-expanded="false" >
          Edit <span class="caret"></span>
        </button>
        <ul class="dropdown-menu">
          <li><a href="#" id="tm-doc-action-duplicate">Duplicate document&hellip;</a></li>
          <li><a href="#" id="tm-doc-action-newblank">New blank document&hellip;</a></li>
          <li role="separator" class="divider"></li>
          <!-- "Rename" saves when closed, so don't allow closing with Esc -->
          <li><a href="#" data-toggle="modal" data-keyboard="false"
            data-target="#renameDialog">Rename&hellip;</a></li>
          <li role="separator" class="divider"></li>
          <li><a href="#" data-toggle="modal" data-target="#deleteDialog">Delete&hellip;</a></li>
        </ul>
      </div>
    </div>
    <!-- Import and "Share" Menu -->
    <div class="navbar-right">
      <button type="button" class="btn btn-default navbar-btn tm-needsready" aria-label="Import" disabled
      data-toggle="modal" data-target="#importPanel"
      data-has-tooltip data-placement="bottom" data-trigger="hover" title="Import">
        <span class="glyphicon glyphicon-folder-open" aria-hidden="true"></span>
      </button>
      <button type="button" class="btn btn-default navbar-btn tm-needsready" aria-label="Share" disabled
      data-toggle="modal" data-target="#exportPanel" data-keyboard="false"
      data-has-tooltip data-placement="bottom" data-trigger="hover" title="Share">
        <span class="glyphicon glyphicon-share" aria-hidden="true"></span>
      </button>
    </div>
  </div>
</nav>
<!-- ** Modal dialogs ** -->
<!-- Dialog for Rename -->
<div id="renameDialog" class="modal" tabindex="-1" role="dialog" aria-labelledby="renameDialogHeader">
  <div class="modal-dialog modal-sm" role="document">
    <div class="modal-content">
      <div class="modal-header">
        <button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">&times;</span></button>
        <h4 class="modal-title" id="renameDialogHeader">Document Name</h4>
      </div>
      <div class="modal-body">
        <form id="renameDialogForm">
          <label class="sr-only" for="renameDialogInput">Document Name</label>
          <input type="text" class="form-control" id="renameDialogInput" placeholder="document name">
        </form>
      </div>
    </div>
  </div>
</div>
<!-- Dialog for Delete -->
<div id="deleteDialog" class="modal fade" tabindex="-1" role="dialog" aria-labelledby="deleteDialogHeader">
  <div class="modal-dialog modal-sm" role="document">
    <div class="modal-content">
      <div class="modal-header">
        <button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">&times;</span></button>
        <h4 class="modal-title" id="deleteDialogHeader">Delete this document?</h4>
      </div>
      <div class="modal-body">
        This will erase the document and remove it from the menu.
        You can’t undo this action.
      </div>
      <div class="modal-footer">
        <button id="tm-doc-action-delete" type="button"
          class="btn btn-danger pull-left" data-dismiss="modal">Delete</button>
        <button type="button" class="btn btn-default" data-dismiss="modal">Cancel</button>
      </div>
    </div>
  </div>
</div>
<!-- Dialog for Resetting an Example -->
<div id="resetExampleDialog" class="modal fade" tabindex="-1" role="dialog" aria-labelledby="resetExampleDialogHeader">
  <div class="modal-dialog" role="document">
    <div class="modal-content">
      <div class="modal-header">
        <button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">&times;</span></button>
        <h4 class="modal-title" id="resetExampleDialogHeader">Save a copy of your changes?</h4>
      </div>
      <div class="modal-body">
        <p>Resetting this example will erase any changes made to it.</p>
        You have the option to save your changes as a new document, or simply discard them.
        You can’t undo this action.
      </div>
      <div class="modal-footer">
        <button id="tm-doc-action-resetdiscard" type="button"
          class="btn btn-danger pull-left" data-dismiss="modal">Discard</button>
        <button type="button" class="btn btn-default" data-dismiss="modal">Cancel</button>
        <button id="tm-doc-action-resetsave" type="button"
          class="btn btn-primary btn-wide-save" data-dismiss="modal">Save</button>
      </div>
    </div>
  </div>
</div>
<!-- Dialog for Import button -->
<div id="importPanel" class="modal fade" tabindex="-1" role="dialog"
aria-labelledby="importPanelHeader">
  <div class="modal-dialog" role="document">
    <div class="modal-content">
      <div class="modal-header">
        <button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">&times;</span></button>
        <h4 class="modal-title" id="importPanelHeader">Import</h4>
      </div>
      <div class="modal-body">
        <div class="panel panel-default">
          <div class="panel-heading">
            <h5 class="panel-title">From GitHub gist</h5>
          </div>
          <div class="panel-body">
            <form id="gistIDForm" class="form-inline">
              <div class="input-group">
                <span class="input-group-addon">https://gist.github.com/</span>
                <input type="text" size="36" class="form-control"
                placeholder="gist ID" spellcheck="false"
                pattern="[\da-fA-F]+" title="Hex digits (0–9, a–f)">
              </div>
              <button type="submit" class="btn btn-default">Import</button>
            </form>
            <span class="help-block">
              If the gist contains multiple documents, you’ll be able to choose which ones to import.
            </span>
          </div>
        </div>
        <div id="importFilesPanel" class="panel panel-default">
          <div class="panel-heading">
            <h5 class="panel-title">From files</h5>
          </div>
          <div class="panel-body">
            <div class="form-group">
              <p>Choose one or more files to import</p>
              <div class="input-group">
                <input type="file" name="files" multiple class="form-control">
                <span class="input-group-btn">
                  <button id="importFilesButton"
                  type="button" class="btn btn-default">Import</button>
                </span>
              </div>
            </div>
            <div class="form-group">
              <p>&hellip;or paste a document’s contents below.</p>
              <textarea class="form-control" rows="8" cols="40"></textarea>
            </div>
            <div class="text-center">
              <button id="importContentsButton"
              type="button" class="btn btn-default">Import</button>
            </div>
          </div>
        </div>
      </div>
    </div>
  </div>
</div>
<!-- Dialog for Sharing/Export -->
<div id="exportPanel" class="modal fade" tabindex="-1" role="dialog" aria-labelledby="exportPanelHeader">
  <div class="modal-dialog" role="document">
    <div class="modal-content">
      <div class="modal-header">
        <button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">&times;</span></button>
        <h4 class="modal-title" id="exportPanelHeader">Share &amp; Export</h4>
      </div>
      <div class="modal-body">
        <div class="panel panel-default">
          <div class="panel-heading">
            <h5 class="panel-title">Share link</h5>
          </div>
          <div class="panel-body">
            <div class="form-group">
              <div id="shareGistContainer">
              </div>
              <p>
                You can link to any GitHub gist by its ID:
              </p>
              <div class="well well-sm">
                <samp>turingmachine.io/?import-gist=<var>ID</var></samp>
              </div>
              <p>
                When using your own gists, you gain the ability to update and delete the contents,
                and to share multiple documents at once.
              </p>
              <a class="disclosure-triangle collapsed" role="button" data-toggle="collapse" href="#customGistInstructions">
                How to make your own gist
              </a>
              <div id="customGistInstructions" class="collapse">
                <ol>
                  <li>Open the <a href="https://gist.github.com" target="_blank">new gist page.</a>
                    Sign into GitHub if you’d like to be able to edit or delete the contents in the future.
                  </li>
                  <li>Download the document (below), then drag &amp; drop it onto the new gist page. <br>
                      Alternatively, copy &amp; paste the contents, and name the file to end with <code>.yaml</code>
                  </li>
                  <li>Create the gist. The gist ID will be at the end of the URL.</li>
                </ol>
              </div>
            </div>
          </div>
        </div>
        <div class="panel panel-default">
          <div class="panel-heading">
            <h5 class="panel-title">Download</h5>
          </div>
          <div class="panel-body">
            <div class="form-group">
              <p>Download the current document to get a backup copy
                to share and import on other browsers and devices.</p>
              <div id="exportDownloadContainer">
              </div>
              <div class="download-fallback">
                <a class="disclosure-triangle collapsed" role="button" data-toggle="collapse" href="#downloadAttrInfo">
                  Why the extra steps?
                </a>
                <div id="downloadAttrInfo" class="help-block collapse icon-help-block">
                  <span class="glyphicon glyphicon-info-sign" aria-hidden="true"></span>
                  <p>Your browser
                    <a href="http://caniuse.com/#feat=download" target="_blank">doesn’t support</a>
                    an HTML5 <a href="https://developer.mozilla.org/en-US/docs/Web/HTML/Element/a#attr-download" target="_blank">feature</a>
                    to mark links as downloadable.
                    Without sending your data to a server—just to have it
                    <a href="https://en.wikipedia.org/wiki/MIME#Content-Disposition" target="_blank">marked</a>
                    and sent back again—the simplest alternative is to save the file manually.
                  </p>
                </div>
              </div>
            </div>
            <div class="form-group">
              <p>The contents of the download are below.</p>
              <button id="copyContentsButton" type="button" class="btn btn-default" data-clipboard-target="#exportTextarea">
                Copy to clipboard
              </button>
            </div>
            <textarea id="exportTextarea"
            class="form-control" rows="8" cols="40" readonly></textarea>
          </div>
        </div>
      </div>
    </div>
  </div>
</div>

<!-- Main Content -->
<div class="container-fluid">
  <div class="row">
    <div id="diagram-column" class="col-md-7 form-group text-center">
      <!-- Diagram -->
      <div id="machine-container" class="form-group">
        <!-- Noscript notice -->
        <noscript>
          <div class="panel panel-default">
            <div class="panel-heading">
              <h3 class="panel-title">Tip: Enable JavaScript</h3>
            </div>
            <div class="panel-body">
              <p>The visualization couldn’t load because JavaScript is disabled.</p>
            </div>
          </div>
        </noscript>
      </div>
      <!-- Simulator controls -->
      <div id="controls-container" class="row text-center">
        <div class="col-xs-1">
          <button type="button" class="btn btn-warning btn-xs text-center tm-btn-diagram tm-reset">
            <span class="glyphicon glyphicon-fast-backward" aria-hidden="true"></span><br>
            Reset
          </button>
        </div>
        <div class="col-xs-2 col-xs-offset-4 text-center">
          <button type="button" class="btn btn-primary text-center tm-btn-diagram tm-step">
            <span class="glyphicon glyphicon-step-forward" aria-hidden="true"></span><br>
            Step
          </button>
        </div>
        <div class="col-xs-1">
          <button type="button" class="btn btn-default text-center tm-btn-diagram tm-run">
            <span class="glyphicon glyphicon-play" aria-hidden="true"></span><br>
            Run
          </button>
        </div>
      </div>
    </div>

    <!-- Code Editor -->
    <div class="col-md-5 form-group text-center">
    <div id="editor-wrapper">
      <div id="editor-alerts-container"></div>
      <button type="button" class="btn btn-primary tm-editor-load">
        Load machine
      </button>
      <button type="button" class="btn btn-default tm-editor-revert">
        Revert to diagram
      </button>
      <div id="editor-container" class="tm-editor"></div>
    </div>
    </div>
  </div>

  <script>
    $(function () {
      $('[data-has-tooltip]').tooltip()
    });
    // Polyfill for IE
    if (!('remove' in Element.prototype)) {
      Element.prototype.remove = function () { if (this.parentNode) { this.parentNode.removeChild(this); } };
    }
  </script>
  <!-- Entry point -->
  <script src="build/TMViz.bundle.js" charset="utf-8"></script>
  <script src="build/main.bundle.js" charset="utf-8"></script>

  <hr>
<!-- Tutorial -->
<div id="tutorial" class="row">
  <section class="col-md-4 col-sm-6">
    <h3>Try it out</h3>
    <p>
      <strong>Run</strong> the machine to see it in action.
      At any time, you can <strong>step</strong> or <strong>pause</strong> to get a closer look,
      or <strong>reset</strong> to start over.
    </p>
    <p>There are over a dozen different example machines to explore.</p>
    <p>
      Most of the examples take input. Experiment with different inputs to see what happens!
      Edit the code and click <em>Load machine</em> to sync your changes.
    </p>
    <section>
      <h4>What’s going on?</h4>
      <p>The colored circles are <em>states</em>. The squares underneath are <em>tape cells</em>.</p>
      <p>The current state and tape cell are highlighted.</p>
      <p>At each step, a Turing machine reads its current state and tape symbol,
      and looks them up in its <em>transition table</em> for an instruction.
      Each <em>instruction</em> does 3 things:</p>
      <ol>
        <li><strong>write</strong> a symbol to the current tape cell</li>
        <li><strong>move</strong> to the left or right by one cell</li>
        <li><strong>set</strong> the new state</li>
      </ol>
      <p>That’s it!</p>
      <p>This repeats step after step, until the machine reaches a combination of state and symbol
        that don’t have an instruction defined. At that point it <em>halts</em>.
      </p>
    </section>
    <section>
      <h4><a href="#tm-details" class="disclosure-triangle collapsed" role="button" data-toggle="collapse">
        In more detail
      </a></h4>
      <div id="tm-details" class="panel-group collapse" role="tablist" aria-multiselectable="true">
        <div class="panel panel-default">
          <div id="headingBasics" class="panel-heading" role="tab">
            <h4 class="panel-title">
              <a role="button" data-toggle="collapse" data-parent="#tm-details" href="#details-basics" aria-controls="details-basics" aria-expanded="true">
                Basics
              </a>
            </h4>
          </div>
          <div id="details-basics" aria-labelledby="headingBasics" class="panel-collapse collapse in" role="tabpanel">
            <div class="panel-body">
              <p>A <dfn>Turing machine</dfn> is an abstract device to model computation as rote symbol manipulation.</p>
              <p>Each machine has a finite number of states, and a finite number of possible symbols.
                These are fixed before the machine starts, and do not change as the machine runs.</p>
              <p>There are an <em>infinite</em> number of tape cells, however, extending endlessly to the left and right.
                Each tape cell bears a symbol. Any cell not part of the input or not yet written to bears the blank symbol by default.
                Notice that at any step, only finitely many cells bear a non-blank symbol.</p>
              <p>(As a mathematical model, a Turing machine has infinite memory (an infinite tape) so as to not artificially restrict its power.
                In practice, many machines of interest take finite memory, and can be fully simulated for manageable input sizes.
                Even machines that use infinite memory—and hence never halt—use at most one new tape cell per step, and so can be simulated to an extent.)</p>
            </div>
          </div>
        </div>
        <div class="panel panel-default">
          <div id="headingFormalDefn" class="panel-heading" role="tab">
            <h4 class="panel-title">
              <a class="collapsed" role="button" data-toggle="collapse" data-parent="#tm-details" href="#details-formal-defn" aria-controls="details-formal-defn" aria-expanded="false">
                Formal definition
              </a>
            </h4>
          </div>
          <div id="details-formal-defn" class="panel-collapse collapse" role="tabpanel" aria-labelledby="headingFormalDefn">
            <div class="panel-body">
              <p>The formal definition of a Turing machine has slight variations but essentially is a tuple (ordered list) comprising</p>
              <ul>
                <li>states Q</li>
                <li>start state q₀ &in; Q</li>
                <li>input alphabet &Sigma;</li>
                <li>tape alphabet &Gamma;, where &Sigma; &subseteq; &Gamma;</li>
                <li>blank symbol b &in; &Gamma;</li>
                <li>transition function &delta; that has the type Q &times; &Gamma; &rightarrow; &Gamma; &times; {L, R} &times; Q</li>
              </ul>
              <p>where Q, &Sigma;, and &Gamma; are finite nonempty sets.
                Some definitions also require that the blank symbol not be part of the input (b &notin; &Sigma;).</p>

              <p>As an example, a formal description for the “binary increment” machine is as follows:</p>
              <p>
                Q = { right, carry, done }
                <br>q₀ = right
                <br>&Sigma; = { 1, 0 }
                <br>&Gamma; = { 1, 0, ' ' }
                <br>b = ' '
              </p>
              <p>
                    &delta;(right, 1)   = (1, R, right)
                <br>&delta;(right, 0)   = (0, R, right)
                <br>&delta;(right, ' ') = (' ', L, carry)
                <br>&delta;(carry, 1)   = (0, L, carry)
                <br>&delta;(carry, 0)   = (1, L, done)
                <br>&delta;(carry, ' ') = (1, L, done)
              </p>
              <p>Note that for simplicity, the simulator limits each symbol to one character.
                Furthermore, input is not checked for conformance with an input alphabet, in exchange for not having to define input and tape alphabets.</p>
              <p>(The behavior of a Turing machine can also be described in mathematical terms if desired.
                Without going into too much detail, this involves defining how a <em>configuration</em>
                of a machine—its state, tape contents, and tape head position (current cell)—leads to the next configuration, based on the transition function.
                To start with, the tape’s contents may be defined as a function from integers to symbols,
                with the head position as an integer, and each move {L, R} adding -1 or +1 respectively to the head position.)</p>
            </div>
          </div>
        </div>
        <div class="panel panel-default">
          <div id="headingVariations" class="panel-heading" role="tab">
            <h4 class="panel-title">
              <a class="collapsed" role="button" data-toggle="collapse" data-parent="#tm-details" href="#details-variations" aria-controls="details-variations" aria-expanded="false">
                Variations
              </a>
            </h4>
          </div>
          <div id="details-variations" class="panel-collapse collapse" role="tabpanel" aria-labelledby="headingVariations">
            <div class="panel-body">
              <p>Some aspects of the definition vary from author to author, but the differences come down to preference and do not affect computational power.
                That is, machines on one model can be simulated or converted to run on another model.</p>
              <p>Some of the variations you may come across:</p>
              <ol>
                <li>The tape only extends infinitely to the right. The left end is where the tape head (current cell) begins.
                  Moving left at the left end keeps the tape head on the same cell.</li>
                <li>In addition to “move left” (L) or “move right” (R), a tape head movement can be “no move” (N).</li>
                <li>Instead of moving the tape head, a movement shifts the tape itself, so that the directions of L &amp; R are swapped.
                  (Shifting the tape left is the same as moving the head right.)</li>
                <li>The machine can only halt in one of two states: a state designated the <em>accept</em> state, or another state designated the <em>reject</em> state.
                  These states have no exiting transitions. All the other states must have transitions defined for every symbol.</li>
              </ol>
              <p>The simulator was designed with these and other considerations in mind.</p>
              <ol>
                <li>Limiting the tape was inconvenient, often requiring marking the left end with a symbol, and writing numbers in reverse.
                  On the other hand, machines created for a right-infinite tape can run on a doubly-infinite tape with little to no modification.</li>
                <li>Compared to L and R, “no move” (N) seems to be seldom used. For now it has been omitted for conceptual simplicity.</li>
                <li>It's more intuitive to set the current cell directly by moving the tape head. Turing also follows this convention.
                  (The visualization however stays centered on the head to avoid issues of the head moving out of view.)</li>
                <li>The accept/reject convention still works; it's just not required.
                  In fact the simulator supports a convenient shorthand, demonstrated in some of the examples:
                  omit the reject state and all transitions to it, and treat halting on a non-accept state as an implicit rejecting transition.
                  This reduces tedious boilerplate code and makes for a cleaner diagram.</li>
              </ol>
            </div>
          </div>
        </div>
      </div>
    </section>
    <p>
      For a very readable introduction to Turing machines, including their significance and interesting implications,
      see the excellent <a href="http://plato.stanford.edu/entries/turing-machine" target="_blank">entry in the Stanford Encyclopedia of Philosophy</a>.
    </p>
  </section>



  <section class="col-md-4 col-sm-6">
    <h3>Make your own</h3>
    <p>Make spinoffs from the examples or your own creations by using
      <i>Edit</i> &gt; <i>Duplicate document</i>.
    You can also start from scratch with a new blank document.</p>
    <p>All it takes to describe a Turing machine is a start state, blank symbol, and transition table.</p>
    <h4>Example</h4>
    <pre>
# Adds 1 to a binary number.
input: '1011'
blank: ' '
start state: right
table:
  # scan to the rightmost digit
  right:
    1: R
    0: R
    ' ': {L: carry}
  # then carry the 1
  carry:
    1: {write: 0, L}
    0: {write: 1, L: done}
    ' ': {write: 1, L: done}
  done:
</pre>
    <p>
      Here the states are <code>right</code>, <code>carry</code>, and <code>done</code>.<br>
      The symbols are '<code>1</code>', '<code>0</code>', and '<code> </code>'.
    </p>
    <p>
      We designate one state the <i>start state</i>,
      and one symbol the <i>blank</i> symbol (found on unmarked tape cells).
    </p>
    <p>
      A state and a symbol together map to an instruction.
      In the <code>carry</code> state, for instance, the symbol <code>1</code> maps to the instruction <code>{write: 0, L}</code>.
      When no instruction is defined, as in the <code>done</code> state, the machine halts.
    </p>
    <h4>Instruction format</h4>
    The general form of an instruction has three parts:
    <pre>{write: <var>symbol</var>, <var>move</var>: <var>state</var>}</pre>
    <ul>
      <li><code>{write: 1, L: done}</code> writes the symbol <code>1</code>,
        moves the tape head left (<code>L</code>), and goes to the <code>done</code> state.
      </li>
    </ul>
    <p>For brevity, you can omit the symbol and state if they stay the same.</p>
    <ul>
      <li><code>{L: carry}</code> writes the same symbol that was read,
        moves the tape head left, and goes to the <code>carry</code> state.</li>
      <li><code>R</code> (shorthand for {R}) simply moves the tape head right.
        It writes back the same symbol and stays in the same state.</li>
    </ul>
  </section>



  <div class="col-md-4 col-sm-12">
    <h3>Tips</h3>
    <div class="row">
    <div class="col-sm-6 col-md-12">
      <h4>Editor keyboard shortcuts</h4>
      <table id="kbdShortcutTable" class="editor-shortcuts table">
      </table>
      <noscript>
        <p>The code editor and keyboard shortcuts require that JavaScript be enabled.</p>
      </noscript>
      <p>More keyboard shortcuts are available on the <a href="https://github.com/ajaxorg/ace/wiki/Default-Keyboard-Shortcuts" target="_blank">full list</a>.</p>
    </div>
    <div class="col-sm-6 col-md-12">
      <h4>Misc. tips</h4>
      <ul id="misc-tips-list">
        <li>Drag or click a state node to fix it in place; double-click to release it.</li>
        <li>Don’t hesitate to duplicate.
          Use <i>Edit</i> &gt; <i>Duplicate document</i> to create a snapshot of your current document whenever you’re about to make a larger edit.</li>
        <li>Changes are autosaved to your browser’s local storage.
          They will stay there between sessions, but be careful when clearing browser data. You can create backups by downloading your documents.</li>
        <li>Incognito / Private Browsing mode uses a separate temporary storage. This is useful for importing or editing documents that you want to try but don’t want to keep.</li>
      </ul>
      <a class="disclosure-triangle collapsed" role="button" data-toggle="collapse" href="#aboutSyntax">
        More about the syntax
      </a>
      <div id="aboutSyntax" class="collapse">
        <p>The code is written in <a href="https://en.wikipedia.org/wiki/YAML" target="_blank"><abbr>YAML</abbr></a> 1.2, a general-purpose data format.</p>
        <p>
          If you’re familiar with JSON, YAML is similar, but designed to be more readable.
          Mappings can use indent instead of brackets <code>{}</code>, and strings can often be included directly without quotes.
        </p>
        <p>
          Some strings need to be quoted: for example, those that start/end with a space, or include certain characters that have special meaning in YAML.
          If a string is causing problems, try putting quotes around it.
        </p>
      </div>
    </div>
    </div>
  </div>
</div>
</div>

<footer class="page-footer">
  <a href="https://github.com/aepsilon/turing-machine-viz" target="_blank" title="View on GitHub">
    <svg class="octicon octicon-mark-github" height="24" width="24" viewBox="0 0 16 16" version="1.1" aria-hidden="true">
      <path d="M8 0C3.58 0 0 3.58 0 8c0 3.54 2.29 6.53 5.47 7.59 0.4 0.07 0.55-0.17 0.55-0.38 0-0.19-0.01-0.82-0.01-1.49-2.01 0.37-2.53-0.49-2.69-0.94-0.09-0.23-0.48-0.94-0.82-1.13-0.28-0.15-0.68-0.52-0.01-0.53 0.63-0.01 1.08 0.58 1.23 0.82 0.72 1.21 1.87 0.87 2.33 0.66 0.07-0.52 0.28-0.87 0.51-1.07-1.78-0.2-3.64-0.89-3.64-3.95 0-0.87 0.31-1.59 0.82-2.15-0.08-0.2-0.36-1.02 0.08-2.12 0 0 0.67-0.21 2.2 0.82 0.64-0.18 1.32-0.27 2-0.27 0.68 0 1.36 0.09 2 0.27 1.53-1.04 2.2-0.82 2.2-0.82 0.44 1.1 0.16 1.92 0.08 2.12 0.51 0.56 0.82 1.27 0.82 2.15 0 3.07-1.87 3.75-3.65 3.95 0.29 0.25 0.54 0.73 0.54 1.48 0 1.07-0.01 1.93-0.01 2.2 0 0.21 0.15 0.46 0.55 0.38C13.71 14.53 16 11.53 16 8 16 3.58 12.42 0 8 0z" />
    </svg>
  </a>
</footer>

<!-- Dialog for Import -->
<div id="importDialog" class="modal fade" tabindex="-1" role="dialog"
aria-labelledby="importDialogHeader">
  <div class="modal-dialog" role="document">
    <div class="modal-content">
      <div class="modal-header">
        <button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">&times;</span></button>
        <h4 class="modal-title" id="importDialogHeader">Import</h4>
      </div>
      <div class="modal-body">
      </div>
      <div class="modal-footer">
      </div>
    </div>
  </div>
</div>
</body>
</html>
